package com.hiwhitley.easy.day11;

import java.util.HashMap;

/**
 * Created by hiwhitley on 2016/8/15.
 */
public class ClimbStairs {

    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public static int climbStairs(int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if (n == 0) {
            map.put(0, 0);
            return 0;
        }
        if (n == 1) {
            map.put(1, 1);
            return 1;
        }
        if (n == 2) {
            map.put(2, 2);
            return 2;
        }
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        map.put(n, result);
        return result;
    }


    public int climbStairs2(int n) {
        int a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            b = a + b;
            a = b - a;
        }
        return b;
    }
    public static void main(String[] args) {
        System.out.println(climbStairs(7));
    }
}
